package 链表和树.二叉树;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//Java：二叉树的层序遍历
public class BinaryTreeLevelOrderTraversal{
    public static void main(String[] args) {
        Solution solution = new BinaryTreeLevelOrderTraversal().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

//  public class TreeNode {
//      int val;
//      TreeNode left;
//      TreeNode right;
//      TreeNode() {}
//      TreeNode(int val) { this.val = val; }
//      TreeNode(int val, TreeNode left, TreeNode right) {
//          this.val = val;
//          this.left = left;
//          this.right = right;
//      }
//  }

class Solution {
    //层序遍历也可以是实现求二叉树的最大深度问题最大深度就是我们最后数组的长度！
    public List<List<Integer>> levelOrder(TreeNode root) {
        //方法一：使用两个数组的写法
        if(root == null){
            return List.of();
        }

        List<List<Integer>> ans = new ArrayList<>();
        List<TreeNode> cur = List.of(root);

        while (!cur.isEmpty()){
            List<TreeNode> nxt = new ArrayList<>();
            List<Integer> vals = new ArrayList<>(cur.size());

            for (TreeNode node : cur) {
                vals.add(node.val);
                if(node.left != null) nxt.add(node.left);
                if(node.right != null) nxt.add(node.right);

            }
            cur = nxt;
            ans.add(vals);
        }

        return ans;


        //方法二：一个队列
        if(root == null){
            return List.of();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()){
            int n = q.size();
            List<Integer> vals = new ArrayList<>(q.size());
            while (n--> 0) {
                TreeNode node = q.poll();
                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);
                vals.add(node.val);
            }
            ans.add(vals);
        }
        return ans;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}